This application is a continuation-in-part of Forney, U.S. patent application Ser. No. 485,069, filed Apr. 14, 1983, U.S. Pat. No. 4,597,090, assigned to the same assignee as this application, and fully incorporated herein by reference.
This invention relates to communication over band-limited channels of the kind in which codes or lattices are used to represent information to be communicated.
A code is a finite set of codewords each made up of a finite sequence of N symbols which are themselves elements of a finite field. For example, in binary codes each symbol in each codeword is one of two elements (typically 0 or 1). A lattice is a set of points (or codewords, or N-tuples), each comprising a finite sequence of N symbols that are drawn from an infinite set (typically, the set of integers).
In communication systems, a so-called coding gain can be attained by mapping groups of information bits to be communicated into codeword points drawn from sets which have certain distance properties. The receiver takes advantage of the distance properties to achieve the coding gain.
Codes and lattices which are relatively long (i.e., in which each codeword or point has a large number of N symbols) offer the prospect for relatively large coding gains (over conventional uncoded modulation systems) but they present extremely complex decoding problems. Examples of such potentially useful codes and lattices are the well-known (24, 12, 8) Golay code and the well-known 24-dimensional Leech lattice.
A so-called (N, K) binary block code has a generator matrix consisting of K N-tuples (rows), whose 2.sup.K binary linear combinations are the 2.sup.K codewords in the code. The so-called dual code of such a code is defined as the set of all N-tuples which are orthogonal to all 2.sup.K codewords, i.e., whose inner product with any codeword in the original code is zero (modulo 2). It has long been known that the dual code is an (N, N-K) code with 2.sup.N-K codewords which are the binary linear combinations of the N-K rows of the parity-check matrix of the original code. That is, the parity-check matrix is a generator matrix for the dual code.
Wolf, Efficient Maximum Likelihood Decoding of Linear Block Codes Using a Trellis, IEEE Trans. on Inf. Theory, Vol. IT-24, No. `January, 1978, discloses a general method for representing block codes by trellis diagrams. Wolf points out that the number of states at any position along the trellis is no more than q.sup.K, where q is the number of possible symbols from which each coordinate of each codeword is drawn, and K is the number of symbols in a codeword. In fact, Wolf shows that the number of such trellis states need be no more than q.sup.N-K where K is the number of information symbols in each codeword, N-K is the number of parity symbols in each codeword, and q.sup.N-K is the number of words in the dual code. Application of his method would be expected to yield, for example, a 2.sup.12 -state trellis for the Golay code.
In Fast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes, IEEE Trans. on Inf. Theory, Vol. IT-28, No. 2, March, 1982, Conway and Sloane gave maximum likelihood decoding methods for simple lattices (N.ltoreq.8) More recently, Conway & Sloane, "Decoding Techniques for Codes and Lattices, Including the Golay Code and the Leech Lattice", IEEE Trans. on Inf. Theory, Vol. IT-32, No. 1, January, 1986, give maximum likelihood decoding procedures for more complicated codes and lattices, including the Golay code and the Leech lattice.